package com.Questions.DP;

import java.util.Arrays;

public class leetcode410 {
    // 设f[i][j] 为前i个字符 分成j段子数组
    public int splitArray(int[] nums, int k) {
        int n=nums.length;
        int[][] f=new int[n+1][k+1];
        for(int i=0;i<=n;++i){// 先赋值为无穷
            Arrays.fill(f[i],Integer.MAX_VALUE);
        }
        int[] sub=new int[n+1];
        for(int i=0;i<n;++i){
            sub[i+1]=sub[i]+nums[i];
        }
        f[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=Math.min(i,k);++j){
                for(int m=0;m<i;++m){
                    f[i][j]=Math.min(f[i][j],Math.max(f[m][j-1],sub[i]-sub[m]));
                }
            }
        }
        return f[n][k];
    }
}
